import random
import string

MAX_LEN = 200

def generate_random_string(length):
    letters = string.ascii_letters + string.digits
    result = ''.join(random.choice(letters) for _ in range(length))
    return result


def gen() -> list:
    """
    HymABvBYtT1L XAwwlfJr00vpT PHXd2iGnx5
    [
        'wPs7BfobHymABvBYtT1LvyZ6CrObPHXd2iGnx5DaDjTkjr3Jc8K1z',
        'NZpcQQvfBhvmAosRvm4nuBQ81HymABvBYtT1LeHXAwwlfJr00vpThNVDfjEnwFkXPHXd2iGnx54zvrJLP1oG1npldaTp1pomO17nS',
        'zT141FPZgt2mK2HvaN1ngkkTV97bsqLsHymABvBYtT1LtTFWqTfs0fcvXAwwlfJr00vpTRn6RQDln3PJ2721c'
    ] 
    HymABvBYtT1L
    12
    """
    common1 = generate_random_string(random.randint(15,17))
    common2 = generate_random_string(random.randint(15,17))
    common3 = generate_random_string(random.randint(10,16))

    st1 = generate_random_string(random.randint(30, 50)) \
        + common1 \
        + generate_random_string(random.randint(30, 50)) \
        + common2 \
        + generate_random_string(random.randint(30, 50))
    
    st2 = generate_random_string(random.randint(30, 35)) \
        + common1 \
        + generate_random_string(random.randint(30, 35)) \
        + common2 \
        + generate_random_string(random.randint(30, 35)) \
        + common3 \
        + generate_random_string(random.randint(30, 35)) 
    
    st3 = generate_random_string(random.randint(30, 50)) \
        + common1 \
        + generate_random_string(random.randint(30, 50)) \
        + common3 \
        + generate_random_string(random.randint(30, 50))
    
    # print(common1, common2, common3)
    result = [st1, st2, st3]
    result = random.sample(result, 3)

    return result


def solution(str1, str2, str3) -> str:
    len1 = len(str1)
    len2 = len(str2)
    len3 = len(str3)
    if len1 == 0 or len2 == 0 or len3 == 0:
        return ''
    
    # 创建一个三维动态规划表
    dp = [[[0 for _ in range(len3+1)] for _ in range(len2+1)] for _ in range(len1+1)]
    
    max_length = 0
    end_index = 0
    
    # 填充动态规划表
    for i in range(1, len1+1):
        for j in range(1, len2+1):
            for k in range(1, len3+1):
                if str1[i-1] == str2[j-1] == str3[k-1]:
                    dp[i][j][k] = dp[i-1][j-1][k-1] + 1
                    if dp[i][j][k] > max_length:
                        max_length = dp[i][j][k]
                        end_index = i
    
    # 提取最长子串
    longest_substring = str1[end_index-max_length:end_index]
    
    return longest_substring

TEST = False

if TEST:
    import time
    t1 = time.time()
    qq = []
    for _ in range(10):
        qq.append(gen())
    t2 = time.time()
    for q in qq:
        r1 = solution(q[0], q[1], q[2])
        print(q, r1, len(r1))
    t3 = time.time()
    print(t2-t1)
    print(t3-t2)
else:
    from Solution import Solution
    s = Solution()

    for _ in range(10):
        c = gen()
        r1 = len(solution(c[0], c[1], c[2]))
        r2 = s.answer(c[0], c[1], c[2])
        if r1 != r2:
            print("Test Failed\nInput:", c, "\nExpected:", r1, "\nGot:", r2)
            exit(1)
    exit(0)